package a_doubleWrite;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 课程表1--有向无环图判断是否有环
 *
 * @author luolidong
 * @version 1.0
 * @create 2021-07-30 11:45
 */
public class L207 {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        //拓扑排序
        //1.创建入度数组,因为0到num-1
        int[] inDegrees = new int[numCourses];
        for (int[] p : prerequisites) {
            inDegrees[p[0]]++;
        }
        //2.创建保存入度为0的队列
        Queue<Integer> queue = new LinkedList<>();
        //入度为0,入队
        for (int i = 0; i < numCourses; i++) {
            if (inDegrees[i] == 0) queue.offer(i);
        }
        //记录入队节点总数
        int count = 0;
        //bfs,入队，出队
        while (!queue.isEmpty()) {
            int poll = queue.poll();
            count++;
            //该poll节点指向的节点的入度数-1
            for (int[] p : prerequisites) {
                if (p[1] == poll) {
                    inDegrees[p[0]]--;
                    //再次判断入度数为0的，入队
                    if (inDegrees[p[0]] == 0) {
                        queue.offer(p[0]);
                    }
                }
            }
        }
        return count == numCourses;
    }
}
